//路径总数: https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=46&tqId=29117&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m < 1 || n < 1) {
            return 0;
        }
        // 申请F(i,j)空间，初始化
        vector<vector<int>> ret(m, vector<int>(n, 1));
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                // F(i,j) = F(i-1,j) + F(i,j-1)
                ret[i][j] = ret[i - 1][j] + ret[i][j - 1];
            }
        }
        return ret[m - 1][n - 1];
    }
};